package leetcode.图论;

import java.util.ArrayList;
import java.util.List;

/**
 * 字符串相乘
 *
 * 本题解法是一个图论操作
 */
public class Test43字符串相乘 {

    public static String multiply(String num1, String num2) {
        /**
         num1的第 i 位(高位从0开始)和 num2 的第 j 位相乘的结果在乘积中的位置是 [i+j, i+j+1]
         例: 123 * 45,  “123”的第1位：2和“45”的第0位：4的乘积是：08。存放在结果的第[1, 2]位中
         index:    0 1 2 3 4

         1 2 3
         *     4 5
         ---------
         1 5
         1 0
         0 5
         ---------
         0 6 1 5
         1 2
         0 8
         0 4
         ---------
         0 5 5 3 5
         这样我们就可以单独都对每一位进行相乘计算把结果存入相应的index中
         https://leetcode-cn.com/problems/multiply-strings/comments/
         https://leetcode.com/problems/multiply-strings/discuss/17605/Easiest-JAVA-Solution-with-Graph-Explanation
         **/

        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        if (n1 < 0 || n2 < 0)
            return "";
        int[] mul = new int[num1.length() + num2.length()];

        for (int i = n1; i >= 0; --i) {
            for (int j = n2; j >= 0; --j) {
                int bitmul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                // 每次得到乘积后还要加上之前的结果，加上之前的低位
                bitmul += mul[i + j + 1];
                // 进位放在 i + j 的位置
                mul[i + j] += bitmul / 10;
                // 余数放在 i + j + 1 的位置
                mul[i + j + 1] = bitmul % 10;
                // 按如上方式组织，便可得到乘积结果在 [i+j, i+j+1] 里面的效果
            }
        }

        StringBuilder sb = new StringBuilder();
        int i = 0;
        // 去掉前导0
        while (i < mul.length - 1 && mul[i] == 0)
            i++;
        for (; i < mul.length; ++i)
            sb.append(mul[i]);
        return sb.toString();
    }


    public static void main(String[] args) {
        String num1 = "123";
        String num2 = "45";

//        String num1 = "123456789";
//        String num2 = "987654321";

//        String num1 = "123456";
//        String num2 = "2468";

        System.out.println(multiply(num1, num2));
//        System.out.println(multiply2(num1, num2));
        System.out.println(multiply3(num1, num2));
    }

    // 逐位相乘，然后错位相加
    // 显然：数据会越界！，只能通过字符串累加
    public static String multiply2(String num1, String num2) {
        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        if (n1 < 0 || n2 < 0)
            return "";
        String up = null;
        String down = null;
        if (num1.length() >= num2.length()) {
            up = num1;
            down = num2;
        } else {
            up = num2;
            down = num1;
        }
        List<Integer> tmpMulti = new ArrayList<>(down.length());
        int upInt = Integer.valueOf(up);
        for (int i = down.length() - 1; i >= 0; i--) {
            int tmpDownInt = Integer.valueOf(String.valueOf(down.charAt(i)));
            int multi = tmpDownInt * upInt;
            tmpMulti.add(multi);
        }
        int times = 10;
        int sum = tmpMulti.get(0);
        for (int i = 1; i < tmpMulti.size(); i++) {
            int r = tmpMulti.get(i) * times;
            tmpMulti.set(i, r);
            sum += r;
            times *= 10;
        }
        return sum + "";
    }

    public static String multiply3(String num1, String num2) {
        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        if (n1 < 0 || n2 < 0) {
            return "";
        }
        String up = null;
        String down = null;
        if (num1.length() >= num2.length()) {
            up = num1;
            down = num2;
        } else {
            up = num2;
            down = num1;
        }

        List<String> list = new ArrayList<>(down.length());
        int counter = 1;
        for (int i = down.length() - 1; i >= 0; i--) {
            StringBuilder builder = new StringBuilder();
            int dummy = 0;
            for (int j = up.length() - 1; j >= 0; j--) {
                int multi = (down.charAt(i) - '0') * (up.charAt(j) - '0');
                int tmpSum = multi + dummy;
                builder.append(tmpSum % 10);
                dummy = tmpSum / 10;
            }
            if (dummy != 0) {
                builder.append(dummy);
            }
            builder = builder.reverse();
            if (counter > 1) {
                for (int k = counter; k > 1; k--) {
                    builder.append(0);
                }
            }
            list.add(builder.toString());
            counter++;
        }

        String i0 = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            StringBuilder builder = new StringBuilder();
            String ii = list.get(i);//ii一定比i0大
            // 遍历较短的字符串
            int dummy = 0;
            // 计算长字符串和短字符串的差值
            int diff = Math.abs(i0.length() - ii.length());
            for (int j = i0.length() - 1; j >= 0; j--) {
                int tmpSum = (ii.charAt(j + diff) - '0') + (i0.charAt(j) - '0') + dummy;
                builder.append(tmpSum % 10);
                dummy = tmpSum / 10;
            }
            // 短的字符串遍历结束，长的字符串还有最高位没有累加
            for (int j = ii.length() - i0.length() - 1; j >= 0; j--) {
                int tmpSum = ii.charAt(j) - '0' + dummy;
                builder.append(tmpSum % 10);
                dummy /= 10;
            }

            while (dummy != 0) {
                builder.append(dummy % 10);
                dummy /= 10;
            }
            i0 = builder.reverse().toString();
        }

        // 除去答案里面数字前缀有 0 的情况
        if (i0.charAt(0) == '0') {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < i0.length(); i++) {
                if (i0.charAt(i) == '0' && builder.length() == 0)
                    continue;
                else
                    builder.append(i0.charAt(i));
            }
            return builder.length() == 0 ? builder.append(0).toString() : builder.toString();
        } else {
            return i0;
        }
    }
}
